package knn;

import com.google.common.collect.HashMultiset;
import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
import com.google.common.collect.Multiset;
import org.apache.commons.math3.linear.MatrixUtils;
import org.apache.commons.math3.linear.RealMatrix;
import org.apache.commons.math3.linear.RealVector;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

/**
 * 作者: LDL
 * 功能说明: k-近邻算法
 * 创建日期: 2015/5/27
 */
public class KNN {

    public static void main(String[] args) throws IOException {
        String[] resultLabels = new String[]{"not at all","in small doeses","in large doeses"};
        KNN knn = new KNN();
        Map<String,Object> fileMap = knn.file2matrix("datingTestSet2.txt");
        RealMatrix dataMatrix = (RealMatrix) fileMap.get("matrix");
        ArrayList<String> labels = (ArrayList<String>) fileMap.get("labels");
        Map<String,Object> autoNormMap = knn.autoNorm(dataMatrix);
        RealMatrix normMatrix = (RealMatrix) autoNormMap.get("newMatrix");

        double hoRatio = 0.01;
        int errorCount = 0;
        int numTestVecs = (int) (normMatrix.getRowDimension()*hoRatio);
        RealMatrix realMatrix = normMatrix.getSubMatrix(numTestVecs,normMatrix.getRowDimension()-1,0,2);
        for (int i = 0; i < numTestVecs; i++) {
            String result = knn.knnTest(normMatrix.getSubMatrix(i, i, 0, 2), realMatrix,labels.subList(numTestVecs, labels.size()), 3);
            if(!result.equals(labels.get(i))){
                errorCount++;
            }
            System.out.println("判断结果是:"+result+",实际结果应该是:"+labels.get(i));
        }
        System.out.println(errorCount);
    }

    /**
     * 测试KNN算法
     * @param testMatrix 待测试数据
     * @param dataMatrix  已训练数据
     * @param lables   数据分类
     * @param k   最近邻居的数目
     * @return
     */
    public static String knnTest(RealMatrix testMatrix,RealMatrix dataMatrix ,List<String> lables,int k){

        /**
         * 建立与已训练矩阵相同维度的矩阵并赋值
         */
        RealMatrix diffMatrix = MatrixUtils.createRealMatrix(dataMatrix.getRowDimension(),dataMatrix.getColumnDimension());

        int rowLength = diffMatrix.getRowDimension();

        for (int row = 0; row < rowLength; row++) {
            diffMatrix.setRowMatrix(row,testMatrix);
        }

        /**
         * 矩阵相减
         */
        diffMatrix = diffMatrix.subtract(dataMatrix);

        /**
         * 遍历矩阵元素求与测试数据的距离
         *
         */
        ArrayList<KNNNode> knnnodes = Lists.newArrayList();
        int length = diffMatrix.getRowDimension();
        for (int i = 0; i < length; i++) {
            KNNNode node = new KNNNode();
            node.setLabel(lables.get(i));
            double[] rows = diffMatrix.getRow(i);
            double distances = 0;
            for (int j =0;j<rows.length;j++){
                distances += Math.pow(rows[j],2);
            }

            node.setDistance(Math.pow(distances,0.5));
            knnnodes.add(node);
        }

        Collections.sort(knnnodes, new Comparator<KNNNode>() {
            public int compare(KNNNode o1, KNNNode o2) {
                double m = o1.getDistance()-o2.getDistance();
                if(m>0){
                    return 1;
                }else if(m<0){
                    return -1;
                }else{
                    return 0;
                }
            }
        });
        /**
         * 获取k个最邻近的元素
         */
        Multiset<String> multiset = HashMultiset.create();
        for (int i = 0; i < k; i++) {
            multiset.add(knnnodes.get(i).getLabel());
        }

        for(String string : multiset.elementSet()){
            return string;
        }
        return null;

    }
    //归一化特征值 newValue = (oldValue-min)/(max-min)
    public Map<String,Object> autoNorm(RealMatrix dataMatrix){
        Map<String,Object> map = Maps.newHashMap();
        RealMatrix minMatrix = getMinMatrix(dataMatrix);
        minMatrix = fillMatrix(dataMatrix,minMatrix);

        RealMatrix maxMatrix = getMaxMatrix(dataMatrix);
        maxMatrix = fillMatrix(dataMatrix,maxMatrix);

        RealMatrix rangeMatrix = maxMatrix.subtract(minMatrix);

        RealMatrix subMatrix = dataMatrix.subtract(minMatrix);

        RealMatrix newMatrix = elementByElementDivision(subMatrix,rangeMatrix);

        map.put("newMatrix",newMatrix);
        map.put("rangeMatrix",rangeMatrix);
        map.put("minMatrix",minMatrix);

        return map;
    }


    /**
     * 获取所有列中的最小值
     * @param dataMatrix 数据矩阵
     * @return realMatrix 最小值矩阵
     */
    public RealMatrix getMinMatrix(RealMatrix dataMatrix){
        int columns = dataMatrix.getColumnDimension();
        double[] minVals = new double[columns];
        for (int i = 0; i < columns; i++) {
            minVals[i] = dataMatrix.getColumnVector(i).getMinValue();
        }

        RealMatrix realMatrix = MatrixUtils.createRowRealMatrix(minVals);
        return realMatrix;
    }

    /**
     * 获取所有列中的最大值
     * @param dataMatrix
     * @return
     */
    public RealMatrix getMaxMatrix(RealMatrix dataMatrix){
        int columns = dataMatrix.getColumnDimension();
        double[] maxVal = new double[columns];
        for (int i = 0; i < columns; i++) {
            maxVal[i] = dataMatrix.getColumnVector(i).getMaxValue();
        }

        RealMatrix realMatrix = MatrixUtils.createRowRealMatrix(maxVal);
        return realMatrix;
    }

    /**
     * 产生于数据矩阵相同维度的新矩阵
     * @param dataMatrix 数据矩阵
     * @param fillMatrix 要填充的数据矩阵
     * @return newMatrix
     */
    public RealMatrix fillMatrix(RealMatrix dataMatrix,RealMatrix fillMatrix){
        int rows = dataMatrix.getRowDimension();
        int colums = dataMatrix.getColumnDimension();
        RealMatrix newMatrix = MatrixUtils.createRealMatrix(rows,colums);
        for (int i = 0; i < rows; i++) {
            newMatrix.setRowMatrix(i, fillMatrix);
        }
        return newMatrix;
    }

    /**
     * 两个矩阵每个元素相除
     * @param matrix 被除矩阵
     * @param vmatrix 除数矩阵
     * @return newMatrix 结果矩阵
     */
    public RealMatrix elementByElementDivision(RealMatrix matrix,RealMatrix vmatrix){

        int rows = matrix.getRowDimension();
        int colums = matrix.getColumnDimension();
        RealMatrix newMatrix = MatrixUtils.createRealMatrix(rows,colums);
        for (int i = 0; i < rows; i++) {
            RealVector v1 = matrix.getRowVector(i);
            RealVector v2 = vmatrix.getRowVector(i);
            RealVector v3 = v1.ebeDivide(v2);
            newMatrix.setRowVector(i,v3);
        }
        return newMatrix;
    }


    /**
     * 从文件读取数据转换为矩阵
     * @param fileName
     * @return
     */
    public Map<String,Object> file2matrix(String fileName) throws IOException {
        String path = KNN.class.getClassLoader().getResource(fileName).getPath();
        Map<String,Object> map = Maps.newHashMap();
        BufferedReader reader = new BufferedReader(new FileReader(new File(path)));
        ArrayList<String> dataLines = Lists.newArrayList();
        ArrayList<String> dataLabels = Lists.newArrayList();
        String line = null;
        while ((line=reader.readLine())!=null){
            dataLines.add(line);
        }

        RealMatrix matrix = MatrixUtils.createRealMatrix(dataLines.size(),3);

        for (int i = 0; i < dataLines.size(); i++) {
            String[] datas = dataLines.get(i).split("\t");
            double[] array = new double[]{Double.parseDouble(datas[0]),Double.parseDouble(datas[1]),Double.parseDouble(datas[2])};
            dataLabels.add(datas[3]);
            matrix.setRow(i,array);
        }

        map.put("labels",dataLabels);
        map.put("matrix",matrix);
        return map;
    }

}
